#include <math.h>
#include <vector>
#include <unordered_set>
#include <iostream>

using std::cout;
using std::endl;
using std::vector;
using std::ostream;
using std::unordered_set;

template <class Container>
void display(const Container & c)
{//形参使用了const关键字，则迭代器也必须要是const的
    typename Container::const_iterator it = c.begin();
    while(it != c.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void test0()
{
    //unordered_set<int> arr2;
    vector<int> arr{19, 1, 23, 37, 68, 55, 11, 14};
    //元素是无序的
    unordered_set<int> numbers(arr.begin(), arr.end());
    display(numbers);
    auto it = numbers.end();
    //--it;//error  不支持双向迭代器
    auto it2 = numbers.begin();
    ++it2;//ok  只支持前向访问迭代器

    //获取装载因子
    cout << "load factor:" << numbers.load_factor() << endl;
    cout << "numbers' size:" << numbers.size() << endl;
    cout << "numbers' buckets:" << numbers.bucket_count() << endl;
    float factor = (float)numbers.size() / numbers.bucket_count();
    cout << "calc load factor:" << factor << endl;

    //打印每一个桶中的元素
    for(int i = 0; i < numbers.bucket_count(); ++i) {
        cout << "bucket[" << i << "]: ";
        auto beg = numbers.begin(i);
        for(; beg != numbers.end(i); ++beg) {
            cout << *beg << "-->";
        }
        cout << endl;
    }

}

void test1()
{
    vector<int> arr{19, 1, 23, 37, 68, 55, 11, 14};
    //元素是无序的
    //当元素的数量等于桶的数量时，底层实现中重新进行扩容操作，并进行rehash
    unordered_set<int> numbers(arr.begin(), arr.end());
    numbers.insert(22);
    numbers.insert(21);
    numbers.insert(31);
    numbers.insert(41);
    numbers.insert(51);
    numbers.insert(61);
    cout << "numbers' size:" << numbers.size() << endl;
    cout << "numbers' buckets:" << numbers.bucket_count() << endl;
}

class Point
{
public:
    Point(int ix = 0, int iy =0)
    : _ix(ix)
    , _iy(iy)
    {
        cout << "Point(int=0,int=0)" << endl;
    }

    Point(const Point & rhs)
    : _ix(rhs._ix)
    , _iy(rhs._iy)
    {
        cout << "Point(const Point & rhs)" << endl;
    }

    Point(Point && rhs)
    : _ix(std::move(rhs._ix))
    , _iy(std::move(rhs._iy))
    {
        cout << "Point(Point&&)" << endl;
    }
    
    friend ostream & operator<<(ostream & os, const Point & rhs);

    double getDistance() const
    {
        return sqrt(_ix * _ix + _iy * _iy);
    }

    int getX() const {  return _ix; }
    int getY() const {  return _iy; }

private:
    int _ix;
    int _iy;
};

//无序关联式容器需要重载自定义类类型的等于符号
bool operator==(const Point & lhs, const Point & rhs)
{
    return (lhs.getX() == rhs.getX() &&
           lhs.getY() == rhs.getY());
}

ostream & operator<<(ostream & os, const Point & rhs)
{
    os << "(" << rhs._ix
       << "," << rhs._iy
       << ")";
    return os;
}

namespace std
{
//针对于std::hash的特化版本, 不只一个
template <>
struct hash<Point> {
    size_t operator()(const Point & rhs) const
    {
        int ix = rhs.getX();
        int iy = rhs.getY();
        //自定义Hash函数
        return (ix * ix << 1) ^ (iy * iy << 1);
    }
};
}//end of namespace std

void test2()
{
    //std::hash<Point>
    //std::equal_to<Point>
    //points的定义没有设置第二个和第三个模板参数，
    //意味着希望直接使用标准库中的默认参数写法
    unordered_set<Point> points;
    points.insert(Point(1, 1));
    points.insert(Point(2, 2));
    points.insert(Point(3, 3));
    points.insert(Point(3, 3));
    points.insert(Point(4, 4));
    points.insert(Point(5, 5));
    display(points);
}

struct MyHasher
{
    size_t operator()(const Point & rhs) const
    {
        int ix = rhs.getX();
        int iy = rhs.getY();
        return (ix * ix << 1) ^ (iy * iy << 1);
    }
};

struct MyComparator
{
    bool operator()(const Point & lhs, const Point &rhs) const
    {
        return (lhs.getX() == rhs.getX() &&
                lhs.getY() == rhs.getY());
    }
};

void test3()
{
    cout << "\n test3()" << endl;
    //自定义第二个和第三个模板参数的写法
    unordered_set<Point, MyHasher, MyComparator> points;
    points.insert(Point(1, 1));
    points.insert(Point(2, 2));
    points.insert(Point(3, 3));
    points.insert(Point(3, 3));
    points.insert(Point(4, 4));
    points.insert(Point(49, 4));
    points.insert(Point(5, 50));
    display(points);
}


int main()
{
    /* test0(); */
    /* test1(); */
    /* test2(); */
    test3();
    return 0;
}

